package 代码随想录.单调栈.每日温度;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class LeetCode739 {
    //暴力
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (temperatures[j] > temperatures[i]) {
                    res[i] = j - i;
                    break;
                }
            }
        }
        return res;
    }

    //单调栈
    public int[] dailyTemperatures1(int[] temperatures) {
        Deque<Integer> stack = new LinkedList<>();
        int len = temperatures.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            int temperature = temperatures[i]; //当前的温度
            //当栈不空，且当前温度大于栈顶温度
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                Integer pop = stack.pop();
                res[pop] = i - pop; //计算下标之间的差值(就是天数之间的差值)
            }
            //若栈为空或者当前温度小于栈顶温度，则直接入栈
            stack.push(i);
        }
        return res;
    }

    public static void main(String[] args) {
        LeetCode739 code739 = new LeetCode739();
        int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] ints = code739.dailyTemperatures(temperatures);
        int[] ints1 = code739.dailyTemperatures1(temperatures);
        System.out.println(Arrays.toString(ints));
        System.out.println(Arrays.toString(ints1));
    }
}
